package gold.digger;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC576 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public static final int factor = 1000000007;

        Map<String, Long> memo = new HashMap<>();

        public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
            long count = dfs(m, n, maxMove, startRow, startColumn);
            return (int) count;
        }

        public long dfs(int m, int n, int curLeftMove, int curRow, int curColumn) {
            if (curRow < 0 || curRow >= m) return 1;
            if (curColumn < 0 || curColumn >= n) return 1;
            if (curLeftMove <= 0) return 0;
            String key = curLeftMove + "_" + curRow + "_" + curColumn;
            if (memo.containsKey(key)) return memo.get(key);

            long curPositionPathCount = 0;
            long upMoveCount = dfs(m, n, curLeftMove - 1, curRow - 1, curColumn);
            long downMoveCount = dfs(m, n, curLeftMove - 1, curRow + 1, curColumn);
            long leftMoveCount = dfs(m, n, curLeftMove - 1, curRow, curColumn - 1);
            long rightMoveCount = dfs(m, n, curLeftMove - 1, curRow, curColumn + 1);

            curPositionPathCount = (curPositionPathCount + upMoveCount) % factor;
            curPositionPathCount = (curPositionPathCount + downMoveCount) % factor;
            curPositionPathCount = (curPositionPathCount + leftMoveCount) % factor;
            curPositionPathCount = (curPositionPathCount + rightMoveCount) % factor;

            memo.put(key, curPositionPathCount);
            return curPositionPathCount;
        }

    }

    public void run() {
        Solution solution = new Solution();
//        System.out.println(solution.findPaths(2, 2, 2, 0, 0));
        System.out.println(solution.findPaths(1, 3, 3, 0, 1));
    }

    public static void main(String[] args) throws Exception {
        LC576 an = new LC576();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
